package question6_10;

/**
 * @description:
 * 给定一个二叉树其中的一个结点，请找出  中序遍历顺序的下一个结点  并且返回。
 * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
 *
 *           a
 *         /   \
 *        b     c
 *       / \   / \
 *      d   e f   g
 *         / \
 *        h   i
 * @author: jhy
 * @time: 2021/5/19 16:28
 */
public class Question8 {


    public static void main(String[] args) {
        /*
            测试用的树
                  1
                 / \
                2   3
               / \
              4   5
         */
        TreeLinkNode root = new TreeLinkNode(1);
        TreeLinkNode node2 = new TreeLinkNode(2);
        TreeLinkNode node3 = new TreeLinkNode(3);
        TreeLinkNode node4 = new TreeLinkNode(4);
        TreeLinkNode node5 = new TreeLinkNode(5);

        root.left = node2;
        root.right = node3;
        node2.next = root;
        node2.left = node4;
        node2.right = node5;
        node3.next = root;
        node4.next = node2;
        node5.next = node2;
        Question8 question8 = new Question8();
        TreeLinkNode res = question8.GetNext(node4);
        System.out.println(res.val);

    }

    //找出中序遍历的下一个节点
    //分3种情况讨论：
    //①如果该节点有右子树，那么他的下一个节点就是他右子树的最左子节点 eg:b的下一个节点为h
    //②如果该节点没有右子树，但是它是它父节点的左子节点，那么它的下一个节点就是他的父节点 eg:d的下一个节点为b
    //③该节点既没有右子树，又是其父节点的右子节点。我们需要沿着指向父节点的指针向上遍历，直到找到一个节点，
    //       该节点是其父节点的左子节点，那么该节点的父节点就是我们要找的下一个节点
    public TreeLinkNode GetNext(TreeLinkNode pNode) {

        //要返回的节点
        TreeLinkNode res = null;
        if(pNode.right != null){
            //第一种情况，有右子树
            TreeLinkNode temp = pNode.right;
            while (temp != null){
                res = temp;
                temp = temp.left;
            }
        }else if(pNode.next != null && pNode.next.left == pNode){
            //第二种情况，该节点没有右子树，但是它是它父节点的左子节点
            return pNode.next;
        }else {
            //第三种情况，该节点既没有右子树，又是其父节点的右子节点
            TreeLinkNode temp = pNode.next;
            while (temp != null){
                if(temp.next != null && temp.next.left == temp){
                    return temp.next;
                }
                temp = temp.next;
            }
        }
        return res;
    }


}
